package com.leetcode.q5;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p> description: desc</p>
 *
 * @author tanzc
 * @date 2022/3/29
 **/
public class LongestPalindrome {
    static Map<String, Map<String, Boolean>> isPalindromeMap = new HashMap<>();

    public String longestPalindrome(String s) {
        Map<String, Boolean> isPalindrome = new HashMap<>();
        isPalindromeMap.put(s, isPalindrome);
        // 把字符串字符存入列表
        char[] chars = s.toCharArray();
        List<Character> characterList = new ArrayList<>();
        for (char c : chars) {
            characterList.add(c);
        }
        // 记录最终回文串索引首末位置
        int l = 0, r = 0;

        for (int i = 0; i < characterList.size(); i++) {
            List<Character> subList = characterList.subList(i + 1, characterList.size());
            // 该字符后续子列表有重复字符，才有回文可能
            if (subList.contains(characterList.get(i))) {
                // i、j确定待检测回文串
                int j = i + subList.lastIndexOf(characterList.get(i)) + 1;
                // 待测串小于已找出的回文串，不予计算
                while (j - i > r - l) {
                    // i、j间子串为回文串
                    if (isPalindromeString(s, characterList, i, j)) {
                        if (j - i > r - l) {
                            r = j;
                            l = i;
                        }
                        break;
                    } else {
                        // i、j间字串不为回文串，则看是否有另外的重复字符，并缩减i、j
                        subList = subList.subList(0, subList.lastIndexOf(characterList.get(i)));
                        if (subList.contains(characterList.get(i))) {
                            j = i + subList.lastIndexOf(characterList.get(i)) + 1;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        isPalindromeMap.remove(s);
        return s.substring(l, r + 1);
    }

    // 洋葱剥皮式自顶向下判断回文串
    public boolean isPalindromeString(String s, List<Character> characterList, int left, int right) {
        if (isPalindromeMap.get(s).containsKey(left + "-" + right)) {
            return isPalindromeMap.get(s).get(left + "-" + right);
        }
        boolean is;
        if (right - left <= 2) {
            is = characterList.get(left).equals(characterList.get(right));
        } else if (characterList.get(left).equals(characterList.get(right))) {
            is = isPalindromeString(s, characterList, left + 1, right - 1);
        } else {
            is = false;
        }
        isPalindromeMap.get(s).put(left + "-" + right, is);
        return is;
    }

    public String longestPalindrome2(String s) {
        Map<String, Boolean> isPalindrome = new HashMap<>();
        isPalindromeMap.put(s, isPalindrome);

        // 记录最终回文串索引首末位置
        int l = 0, r = 0;

        for (int i = 0; i < s.length(); i++) {
            String subs = s.substring(i + 1);
            if (subs.indexOf(s.charAt(i)) != -1) {
                int j = i + subs.lastIndexOf(s.charAt(i)) + 1;
                while (j - i > r - l) {
                    if (isPlaindromeString2(s, i, j)) {
                        r = j;
                        l = i;
                        break;
                    } else {
                        subs = subs.substring(0, subs.lastIndexOf(s.charAt(i)));
                        if (subs.indexOf(s.charAt(i)) != -1) {
                            j = i + subs.lastIndexOf(s.charAt(i)) + 1;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        isPalindromeMap.remove(s);
        return s.substring(l, r + 1);
    }

    public boolean isPlaindromeString2(String s, int left, int right) {
        if (isPalindromeMap.get(s).containsKey(left +"-" + right)) {
            return isPalindromeMap.get(s).get(left + "-" + right);
        }
        boolean is;
        if (s.charAt(left) == s.charAt(right)) {
            if (right - left <= 2) {
                is = true;
            } else {
                is = isPlaindromeString2(s, left + 1, right - 1);
            }
        } else {
            is = false;
        }
        isPalindromeMap.get(s).put(left + "-" + right, is);
        return is;
    }
}
